#include<iostream>
#include<stack>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
	int len;
	vector<vector<int> >dp;
	vector<vector<string> >ans;
    vector<string>temp;
    bool isPalindrome(string& s,int left,int right){
    	while(left<right)
    	if(s[left++]!=s[right--])
    		return false;
    	return true;
	}
	void dfs(string& s,int i){
		if(i==len){
			ans.push_back(temp);
			return;
		}
		for(int j=i;j<len;j++)
		if(dp[i][j])
		/*if(isPalindrome(s,i,j))*/{
			temp.push_back(s.substr(i,j-i+1));
			dfs(s,j+1);
			temp.pop_back();
		}
	}
    vector<vector<string> > partition(string s) {
		len=s.length();
		dp.assign(len,vector<int>(len,true));
		for(int i=len-1;i>=0;i--)
		for(int j=i+1;j<len;j++)
			dp[i][j]=(s[i]==s[j])&&dp[i+1][j-1];
		dfs(s,0);
        return ans;
    }
}; 
int main(){
	
	return 0;
}
